package com.javabasic.algorithm.sword_of_offer;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/14 8:57 上午
 * @see
 */
public class 找到小镇的法官 {

    /**
     * 总结：换一种思路可以把数据转换为一个人信任了多少人 以及 被多少人信任
     * 结果就是找到被n-1个人信任且其不信任任何人的人
     * @param n
     * @param trust
     * @return
     */
    public int findJudge(int n, int[][] trust) {
        /**
         * dp数组含义表示下标为i的人被多少人信任
         */
        int[] dp = new int[n+1];
        /**
         * trustPerson数组含义表示下标为i的人信任了多少个人
         */
        int[] trustPerson = new int[n+1];
        int len = trust.length;
        for (int i = 0; i < len; i++) {
            dp[trust[i][1]]++;
            trustPerson[trust[i][0]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (dp[i] == n-1 && trustPerson[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}
